package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-29 15:37
 */
public class Test26 {
    public static void main(String[] args) {

    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    /**
     * 尝试双指针
     * a+n(b+c)+b=a+(n+1)b+nc
     * a+(n+1)b+nc=2(a+b) -> a = c + (n - 1)(b + c)
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode p1 = head;//1步
        ListNode p2 = head;//2步

        do {
            if (p2 == null || p2.next == null) {
                return null;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        } while (p1 != p2);
        ListNode ptr = head;
        while (ptr != p1) {
            ptr = ptr.next;
            p1 = p1.next;
        }
        return p1;
    }

//    /**
//     * 哈希表方法
//     *
//     * @param head
//     * @return
//     */
//    public ListNode detectCycle(ListNode head) {
//        if (head == null || head.next == null) {
//            return null;
//        }
//        Set<ListNode> set = new HashSet<>();
//        while (head != null) {
//            if (set.contains(head)) {
//                return head;
//            }
//            set.add(head);
//            head = head.next;
//        }
//        return null;
//    }

}
